public class Leetcode {
}

//leetcode:14:最长公共前缀
class Solution1 {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length ==0){
            return "";
        }
        String s = strs[0];
        for(int i=0;i<strs.length;i++){
            String str = strs[i].toString();
            while(!str.startsWith(s)){
                if(s.length()==0){
                    return "";
                }
                s = s.substring(0,s.length()-1);
            }
        }
        return s;
    }
}
//leetcode:14:最长回文子串
class Solution2 {
    public String longestPalindrome(String s) {
        int begin = 0,len = 0,n = s.length();
        for(int i = 0; i < n;i++){
            int left = i,right = i;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt((right))){
                left--;
                right++;
            }
            if(right-left-1 > len){
                begin = left+1;
                len = right-left-1;
            }

            left = i;right = i+1;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            if(right-left-1 > len){
                begin = left+1;
                len = right-left-1;
            }
        }
        return s.substring(begin,begin+len);
    }
}

//leetcode:67:二进制求和
class Solution3 {
    public String addBinary(String a, String b) {
        int n = Math.max(a.length(),b.length());
        int cnt = 0;
        StringBuilder s = new StringBuilder();
        for(int i = 0;i < n;i++){
            cnt+=i < a.length() ? (a.charAt(a.length()-1-i)-'0'): 0;
            cnt+=i < b.length() ? (b.charAt(b.length()-1-i)-'0'): 0;
            s.append(cnt%2);
            cnt/=2;
        }
        if(cnt > 0){
            s.append('1');
        }
        s.reverse();
        return s.toString();
    }
}

//leetcode:43:字符串相乘
class Solution4 {
    public String multiply(String num1, String num2) {
        char[] s1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] s2 = new StringBuffer(num2).reverse().toString().toCharArray();
        int m = s1.length;
        int n = s2.length;
        int[] tmp = new int[m+n-1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i+j] += (s1[i] - '0') * (s2[j] - '0');
            }
        }

        int x = 0;
        int cnt = 0;
        StringBuffer ret = new StringBuffer();
        while (x < m+n-1 || cnt != 0) {
            if(x < m+n-1) cnt += tmp[x++];
            ret.append((char)(cnt % 10 + '0'));
            cnt /= 10;
        }

        while (ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
            ret.deleteCharAt(ret.length()-1);
        }
        return ret.reverse().toString();
    }
}